﻿'''
题目描述
MELON有一堆精美的雨花石（数量为n，重量各异），准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON
确认是否能将雨花石平均分配。
输入描述
第1行输入为雨花石个数: n，0 < n < 31.
第2行输入为空格分割的各雨花石重量: m[0] m[1] … m[n - 1]， 0 < m[k] < 1001
不需要考虑异常输入的情况。
输出描述
如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等:如果不能均分，则输出-1。
用例1
输入
4
1 1 2 2
输出
2
说明
输入第一行代表共4颗雨花石，第二行代表4颗雨花石重量分别为1、1、2、2。均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，
所以输出2。
用例2
输入
10
1 1 1 1 1 9 8 3 7 10
输出
3
说明
输入第一行代表共10颗雨花石，第二行代表4颗雨花石重量分别为1、1、1、1、1、9、8、3、7、10 。
均分时可以1,1,1,1,1,9,7和10,8,3，也可以1,1,1,1,9.8和10,7,3,1，或者其他均分方式，但第一种只需要拿出重量为10.8,3的3块雨花
石，第二种需要拿出4块，所以输出3(块数最少)。
01背包问题的思路：
题目要求将雨花石平均分配，即找到一种方法，使得从雨花石中拿出最少的数量，使得两堆雨花石的重量相等。这个问题可以转化为一
个01背包问题：从给定的雨花石中选取一些，使得它们的重量之和等于总重量的一半，且选取的雨花石数量最少。
01背包问题的核心思路是使用动态规划。具体步骤如下：
计算所有雨花石的总重量。如果总重量为奇数，那么无法将雨花石平均分配，直接输出-1。
如果总重量为偶数，我们的目标是找到一些雨花石，使得它们的重量之和等于总重量的一半。定义一个动态规划数组dp，其中dp[j]表示
从雨花石中选取一些，使得它们的重量之和为j时，所需的最少雨花石数量。

初始化dp数组，将除了dp[0]之外的其他元素设置为n，表示最坏情况下需要拿出所有雨花石。
遍历每一块雨花石，对于每一块雨花石，从targetWeight开始递减，更新dp数组。如果使用当前雨花石能够减少所需雨花石数量，则更新
dp[j]。
最后，检查dp[targetWeight]的值。如果它等于n，表示无法找到满足条件的雨花石组合，输出-1。否则，输出dp[targetWeight]，表示
从当前雨花石中最少拿出几块，可以使两堆的重量相等。
'''
#读取输入
n = int(input())
weights = list(map(int,input().split()))
#计算雨花石的总重量
total_weight = sum(weights)
if total_weight % 2 != 0:   #不能平分
    print(-1)
    exit()
target_weight = total_weight // 2
#定义dp数组，初始化为0,注意个数为target_weight+1,分别对应不同重量最少可以由多少块雨花石构成，dp[0]用来实现当有重量为i的
#雨花石时dp[i] = dp[i - i] + 1,即dp[i]可以由最少1块雨花石构成
dp = [0] * (target_weight + 1)
#默认1-target_weight最多可以由n块构成
for i in range(1, target_weight + 1):
    dp[i] = n

#遍历雨花石，更新dp数组
for i in range(1, n + 1):
    current_weight = weights[i - 1]
    for j in range(target_weight,current_weight - 1, -1):
        #如果当前重量可以由当前的雨花石和之前的构成，则更新dp为较小的组成个数
        dp[j] = min(dp[j],dp[j - current_weight] + 1)
#输出目标重量的最小雨花石构成个数
if dp[target_weight] == n:  #数量为最大，不可分割
    print(-1)
    exit()
else:
    print(dp[target_weight])